﻿//给你一个 n x n 的 方形 整数数组 matrix ，请你找出并返回通过 matrix 的下降路径 的 最小和 。
//
//下降路径 可以从第一行中的任何元素开始，并从每一行中选择一个元素。
//在下一行选择的元素和当前行所选元素最多相隔一列（即位于正下方或者沿对角线向左或者向右的第一个元素）。
//具体来说，位置(row, col) 的下一个元素应当是(row + 1, col - 1)、(row + 1, col) 
//或者(row + 1, col + 1) 。
//
//输入：matrix = [[2, 1, 3], [6, 5, 4], [7, 8, 9]]
//输出：13
//
//输入：matrix = [[-19, 57], [-40, -5]]
//输出： - 59
//
//提示：
//	n == matrix.length == matrix[i].length
//	1 <= n <= 100
//	- 100 <= matrix[i][j] <= 100

class Solution {
public:
    int minFallingPathSum(vector<vector<int>>& matrix) {
        // 1. 创建 dp 表
        // 2. 初始化
        // 3. 填表
        // 4. 返回结果
        int n = matrix.size();
        vector<vector<int>> dp(n + 1, vector<int>(n + 2, INT_MAX));
        // 初始化第⼀⾏
        for (int j = 0; j < n + 2; j++)
            dp[0][j] = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                dp[i][j] =
                min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i - 1][j + 1])) +
                matrix[i - 1][j - 1];
        int ret = INT_MAX;
        for (int j = 1; j <= n; j++)
            ret = min(ret, dp[n][j]);

        return ret;
    }
};
